<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <title>二叉树 | Hexo</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  <meta name="description" content="一、二叉树的结构12345678struct TreeNode&amp;#123;    int val;    TreeNode* parent;    TreeNode* left;    TreeNode* right;    TreeNode(int x) : val(x), parent(NULL), left(NULL), right(NULL) &amp;#123;&amp;#125;&amp;#125;; 树的性">
<meta property="og:type" content="article">
<meta property="og:title" content="二叉树">
<meta property="og:url" content="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1701%20%E7%AC%AC%E4%B8%83%E7%AB%A0%20%E6%A0%91%20%E4%BA%8C%E5%8F%89%E6%A0%91/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="一、二叉树的结构12345678struct TreeNode&amp;#123;    int val;    TreeNode* parent;    TreeNode* left;    TreeNode* right;    TreeNode(int x) : val(x), parent(NULL), left(NULL), right(NULL) &amp;#123;&amp;#125;&amp;#125;; 树的性">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2021-12-12T06:46:54.000Z">
<meta property="article:modified_time" content="2022-02-05T04:25:01.572Z">
<meta property="article:author" content="John Doe">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/notes-on-computer-expertise/atom.xml" title="Hexo" type="application/atom+xml">
  
  
    <link rel="shortcut icon" href="/notes-on-computer-expertise/favicon.png">
  
  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/typeface-source-code-pro@0.0.71/index.min.css">

  
  
<link rel="stylesheet" href="/notes-on-computer-expertise/css/style.css">

  
    
<link rel="stylesheet" href="/notes-on-computer-expertise/fancybox/jquery.fancybox.min.css">

  
<meta name="generator" content="Hexo 5.4.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/notes-on-computer-expertise/" id="logo">Hexo</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/notes-on-computer-expertise/">Home</a>
        
          <a class="main-nav-link" href="/notes-on-computer-expertise/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/notes-on-computer-expertise/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="https://goofyer.gitee.io/notes-on-computer-expertise"></form>
      </div>
    </div>
  </div>
</header>

      <div class="outer">
        <section id="main"><article id="post-数据结构/1701 第七章 树 二叉树" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1701%20%E7%AC%AC%E4%B8%83%E7%AB%A0%20%E6%A0%91%20%E4%BA%8C%E5%8F%89%E6%A0%91/" class="article-date">
  <time class="dt-published" datetime="2021-12-12T06:46:54.000Z" itemprop="datePublished">2021-12-12</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">数据结构基础知识</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="p-name article-title" itemprop="headline name">
      二叉树
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="一、二叉树的结构"><a href="#一、二叉树的结构" class="headerlink" title="一、二叉树的结构"></a>一、二叉树的结构</h1><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">TreeNode</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">int</span> val;</span><br><span class="line">    TreeNode* parent;</span><br><span class="line">    TreeNode* left;</span><br><span class="line">    TreeNode* right;</span><br><span class="line">    <span class="built_in">TreeNode</span>(<span class="keyword">int</span> x) : <span class="built_in">val</span>(x), <span class="built_in">parent</span>(<span class="literal">NULL</span>), <span class="built_in">left</span>(<span class="literal">NULL</span>), <span class="built_in">right</span>(<span class="literal">NULL</span>) &#123;&#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="树的性质"><a href="#树的性质" class="headerlink" title="树的性质"></a>树的性质</h2><ul>
<li>树具有如下最基本的性质:<script type="math/tex; mode=display">
\text{1)树中的结点数等于所有结点的度数加l。}\\
\text{2)度为m的树中第i层上至多有}m^{i-1}\text{个结点(i≥1)}。\\
\text{3)高度为h的m叉树至多有}\frac{m^h-1}{m-1} \text{个结点}\\
\text{4)具有n个结点的m义树的最小高度为}\log_{m}{(n(m-1)+1)}</script></li>
</ul>
<p>”。γP深度乙差不超过1。<br>3.<br>二叉树的性质<br>非空二叉树 上的叶子结点数等于度为2的结点数加，即no=m2+1。<br>证明:<br>设度为0、1和2的结点个数分别为no. n和n2:结点总数n=<br>no+n +n2.<br>再着二又树中的分支数，除根结点外，其余结点都有一个分支进入，设B为分支总数，<br>则n=B+</p>
<ol>
<li>由于这些分支是由度为1或2的结点射出的，所以又有B=n+2ng.<br>于是得no<br>+n+n2=n+2n2+ 1，则no=n2+1.<br>注意:<br>该结论经常在选择题中用到，希望考生牢记并灵活应用。<br>，空二叉树上第大层上至名有2-个结点(k3D.<br>高度为力的又树年名行2” !个结点(h21)。<br>3)<br>时完个二叉树按从上:到下、从左到右的顺序依次编号12..n则有以下关系:<br>4)<br>对1&gt; 1时，结点i的双亲结点编号xLi2J,即当i为偶数时，其双亲结点的编号为12.<br>它是双亲结点的左孩子:当i为奇数时，其双亲结点的编号为(- 1)12, 它是双亲结点<br>的右孩子。<br>2的1≤n时，结点的左孩子编号为2.在则无左孩子。<br>当241时，结点:的右孩子编号为21+1.1否则无右孩子。<br>国结点:所在层次(深度)为Lg;iti<br>3)具有n个(n&gt;0)结点的完全二<br>.叉树的高度为[log:(n+ 11或LogunI+ 1。</li>
</ol>
<h1 id="二、二叉树的操作"><a href="#二、二叉树的操作" class="headerlink" title="二、二叉树的操作"></a>二、二叉树的操作</h1><h2 id="2-1-先序遍历-中序遍历构建二叉树"><a href="#2-1-先序遍历-中序遍历构建二叉树" class="headerlink" title="2.1 先序遍历+中序遍历构建二叉树"></a>2.1 先序遍历+中序遍历构建二叉树</h2><ul>
<li>先序遍历（PreOrder）的操作过程如下:若二叉树为空，则什么也不做;否则,<ul>
<li>1)访问根结点;</li>
<li>2）先序遍历左子树;</li>
<li>3）先序遍历右子树。</li>
</ul>
</li>
<li>中序遍历（InOrder）的操作过程如下:若二叉树为空，则什么也不做;否则,<ul>
<li>1)中序遍历左子树;</li>
<li>2)访问根结点;</li>
<li>3)中序遍历右子树。对应的递归算法如下:</li>
</ul>
</li>
<li>后序遍历（PostOrder）的操作过程如下:若二叉树为空，则什么也不做;否则,<ul>
<li>1)后序遍历左子树;</li>
<li>2)后序遍历右子树;</li>
<li>3)访问根结点。<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode* <span class="title">reConstructBinaryTree</span><span class="params">(TreeNode* node, vector&lt;<span class="keyword">int</span>&gt; pre, vector&lt;<span class="keyword">int</span>&gt; vin)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (pre.<span class="built_in">size</span>() &lt; <span class="number">1</span>)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> c = pre[<span class="number">0</span>];</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; vin2;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; vin3;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; pre2;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; pre3;</span><br><span class="line">        <span class="keyword">bool</span> ispre = <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">int</span> j = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; vin.<span class="built_in">size</span>(); i++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (vin[i] == c) &#123; ispre = <span class="literal">true</span>; <span class="keyword">continue</span>; &#125;</span><br><span class="line">            <span class="keyword">if</span> (ispre == <span class="literal">false</span>) &#123; vin2.<span class="built_in">push_back</span>(vin[i]); pre2.<span class="built_in">push_back</span>(pre[j]); j++; &#125;</span><br><span class="line">            <span class="keyword">if</span> (ispre == <span class="literal">true</span>) &#123; vin3.<span class="built_in">push_back</span>(vin[i]); pre3.<span class="built_in">push_back</span>(pre[j]); j++; &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        node = <span class="keyword">new</span> <span class="built_in">TreeNode</span>(pre[<span class="number">0</span>]);</span><br><span class="line"></span><br><span class="line">        node-&gt;left = <span class="built_in">reConstructBinaryTree</span>(node-&gt;left, pre2, vin2);</span><br><span class="line">        node-&gt;right = <span class="built_in">reConstructBinaryTree</span>(node-&gt;right, pre3, vin3);</span><br><span class="line">        <span class="keyword">return</span> node;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
</ul>
</li>
</ul>
<h2 id="2-2-二叉树的下一个节点"><a href="#2-2-二叉树的下一个节点" class="headerlink" title="2.2 二叉树的下一个节点"></a>2.2 二叉树的下一个节点</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode* <span class="title">GetNext</span><span class="params">(TreeNode* pNode)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">NULL</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-3-打印二叉树"><a href="#2-3-打印二叉树" class="headerlink" title="2.3 打印二叉树"></a>2.3 打印二叉树</h2><h3 id="2-3-1-第一种方法"><a href="#2-3-1-第一种方法" class="headerlink" title="2.3.1 第一种方法"></a>2.3.1 第一种方法</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line">vector&lt;vector&lt;<span class="keyword">int</span>&gt; &gt; <span class="built_in">Print2</span>(TreeNode* pRoot) </span><br><span class="line">&#123;</span><br><span class="line">    stack&lt;TreeNode*&gt; sta;</span><br><span class="line">    queue&lt;TreeNode*&gt; q;</span><br><span class="line">    vector&lt;vector&lt;<span class="keyword">int</span>&gt;&gt;p;</span><br><span class="line">    <span class="keyword">if</span> (pRoot == <span class="literal">NULL</span>)<span class="keyword">return</span> p;</span><br><span class="line">    q.<span class="built_in">push</span>(pRoot);</span><br><span class="line">    vector&lt;<span class="keyword">int</span>&gt;v;</span><br><span class="line">    <span class="keyword">int</span> m = <span class="number">1</span>;</span><br><span class="line">    m:</span><br><span class="line">    <span class="keyword">while</span> (q.<span class="built_in">size</span>() &gt; <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        TreeNode* a = q.<span class="built_in">front</span>();</span><br><span class="line">        q.<span class="built_in">pop</span>();</span><br><span class="line">        v.<span class="built_in">push_back</span>(a-&gt;val);</span><br><span class="line">        <span class="keyword">if</span> (m == <span class="number">1</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (a-&gt;left != <span class="literal">NULL</span>)sta.<span class="built_in">push</span>(a-&gt;left);</span><br><span class="line">            <span class="keyword">if</span> (a-&gt;right != <span class="literal">NULL</span>)sta.<span class="built_in">push</span>(a-&gt;right);</span><br><span class="line">            m = <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (a-&gt;right != <span class="literal">NULL</span>)sta.<span class="built_in">push</span>(a-&gt;right);</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (a-&gt;left != <span class="literal">NULL</span>)sta.<span class="built_in">push</span>(a-&gt;left);</span><br><span class="line">            m = <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    p.<span class="built_in">push_back</span>(v);</span><br><span class="line">    v.<span class="built_in">clear</span>();</span><br><span class="line">    <span class="keyword">if</span> (sta.<span class="built_in">size</span>() == <span class="number">0</span>)<span class="keyword">return</span> p;</span><br><span class="line">    <span class="keyword">while</span> (sta.<span class="built_in">size</span>() &gt; <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        q.<span class="built_in">push</span>(sta.<span class="built_in">top</span>());</span><br><span class="line">            sta.<span class="built_in">pop</span>();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">goto</span> m;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="2-3-2-第二种方法-顺序打印-栈存储每行信息"><a href="#2-3-2-第二种方法-顺序打印-栈存储每行信息" class="headerlink" title="2.3.2 第二种方法 顺序打印  栈存储每行信息"></a>2.3.2 第二种方法 顺序打印  栈存储每行信息</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">vector&lt;vector&lt;int&gt; &gt; Print(TreeNode* pRoot)</span><br><span class="line">&#123;</span><br><span class="line">    queue&lt;TreeNode*&gt; q, q2;</span><br><span class="line">    vector&lt;vector&lt;int&gt;&gt;p;</span><br><span class="line">    if (pRoot == NULL)return p;</span><br><span class="line">    q.push(pRoot);</span><br><span class="line">    vector&lt;int&gt;v;</span><br><span class="line">m:</span><br><span class="line">    while (q.size() &gt; 0)</span><br><span class="line">    &#123;</span><br><span class="line">        TreeNode* a = q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        v.push_back(a-&gt;val);</span><br><span class="line">        if (a-&gt;left != NULL)q2.push(a-&gt;left);</span><br><span class="line">        if (a-&gt;right != NULL)q2.push(a-&gt;right);</span><br><span class="line">    &#125;</span><br><span class="line">    p.push_back(v);</span><br><span class="line">    v.clear();</span><br><span class="line">    if (q2.size() == 0)return p;</span><br><span class="line">    while (q2.size() &gt; 0)</span><br><span class="line">    &#123;</span><br><span class="line">        q.push(q2.front());</span><br><span class="line">        q2.pop();</span><br><span class="line">    &#125;</span><br><span class="line">    goto m;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-4-先序遍历"><a href="#2-4-先序遍历" class="headerlink" title="2.4 先序遍历"></a>2.4 先序遍历</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">PreBinaryTree</span><span class="params">(TreeNode*root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    vector&lt;<span class="keyword">int</span>&gt; c;</span><br><span class="line">    stack&lt;TreeNode*&gt; s;</span><br><span class="line">    s.<span class="built_in">push</span>(root);</span><br><span class="line">    <span class="keyword">while</span> (s.<span class="built_in">size</span>() &gt; <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">auto</span> i = s.<span class="built_in">top</span>();</span><br><span class="line">        s.<span class="built_in">pop</span>();</span><br><span class="line">        c.<span class="built_in">push_back</span>(i-&gt;val);</span><br><span class="line">        <span class="keyword">if</span> (i-&gt;left)s.<span class="built_in">push</span>(i-&gt;left);</span><br><span class="line">        <span class="keyword">if</span> (i-&gt;right)s.<span class="built_in">push</span>(i-&gt;right);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> c;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-5-中序遍历"><a href="#2-5-中序遍历" class="headerlink" title="2.5 中序遍历"></a>2.5 中序遍历</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">MidBinaryTree</span><span class="params">(TreeNode* root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root == <span class="literal">nullptr</span>)<span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span> (root-&gt;left)<span class="built_in">MidBinaryTree</span>(root-&gt;left);</span><br><span class="line">    c.<span class="built_in">push_back</span>(root);</span><br><span class="line">    <span class="keyword">if</span> (root-&gt;right)<span class="built_in">MidBinaryTree</span>(root-&gt;right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-6-请找出其中的第k小的结点"><a href="#2-6-请找出其中的第k小的结点" class="headerlink" title="2.6 请找出其中的第k小的结点"></a>2.6 请找出其中的第k小的结点</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">TreeNode* KthNode(TreeNode* pRoot, int k)</span><br><span class="line">&#123;</span><br><span class="line">    MidBinaryTree(pRoot);</span><br><span class="line">    return c[k - 1];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-7-删除二叉树"><a href="#2-7-删除二叉树" class="headerlink" title="2.7 删除二叉树"></a>2.7 删除二叉树</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Clear</span><span class="params">(TreeNode* pRoot)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (pRoot == <span class="literal">nullptr</span>)<span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span> (pRoot-&gt;left != <span class="literal">nullptr</span>) &#123;</span><br><span class="line">        <span class="built_in">Clear</span>(pRoot-&gt;left); </span><br><span class="line">        <span class="keyword">delete</span> pRoot-&gt;left;</span><br><span class="line">        pRoot-&gt;left = <span class="literal">nullptr</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (pRoot-&gt;right != <span class="literal">nullptr</span>) &#123;</span><br><span class="line">        <span class="built_in">Clear</span>(pRoot-&gt;right);</span><br><span class="line">        <span class="keyword">delete</span> pRoot-&gt;right; </span><br><span class="line">        pRoot-&gt;right = <span class="literal">nullptr</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">delete</span> pRoot;</span><br><span class="line">    pRoot = <span class="literal">NULL</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1701%20%E7%AC%AC%E4%B8%83%E7%AB%A0%20%E6%A0%91%20%E4%BA%8C%E5%8F%89%E6%A0%91/" data-id="cl403sxs9003jf8vucjmt1hb6" data-title="二叉树" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1203%20%E7%AC%AC%E4%BA%8C%E7%AB%A0%E7%BA%BF%E6%80%A7%E8%A1%A8-%E9%93%BE%E8%A1%A8/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          第二章线性表-链表
        
      </div>
    </a>
  
  
    <a href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2001%20%E6%8E%92%E5%BA%8F/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">二叉树</div>
    </a>
  
</nav>

  
</article>


</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Categories</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/C-%E5%B7%A5%E5%85%B7/">C#工具</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/C-%E5%B7%A5%E5%85%B7/">C++工具</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/Mysql/">Mysql</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/blender/">blender</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/linux/">linux</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/manim/">manim</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/spring/">spring</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/vba%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/">vba基础操作</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E5%88%9B%E9%80%A0%E6%A8%A1%E5%BC%8F/">创造模式</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/">操作系统</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">操作系统基础知识</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E5%BC%80%E5%8F%91/">操作系统开发</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E5%AD%A6/">数学</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">数据结构基础知识</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%A8%A1%E6%9D%BF/">模板</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0/">深度学习</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E8%8B%B1%E8%AF%AD/">英语</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E8%99%9A%E5%B9%BB4/">虚幻4</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/">计算机组成原理</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C/">计算机网络</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/notes-on-computer-expertise/tags/C/" rel="tag">C++</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/notes-on-computer-expertise/tags/C/" style="font-size: 10px;">C++</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/notes-on-computer-expertise/archives/2022/05/">May 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/notes-on-computer-expertise/archives/2022/03/">March 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/notes-on-computer-expertise/archives/2022/02/">February 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/notes-on-computer-expertise/archives/2022/01/">January 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/notes-on-computer-expertise/archives/2021/12/">December 2021</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/notes-on-computer-expertise/2022/05/31/vue/%E5%89%8D%E7%AB%AF%E6%A1%86%E6%9E%B6%E9%AA%8C%E8%AF%81%E7%A0%81%E6%97%A0%E6%B3%95%E6%98%BE%E7%A4%BA/">(no title)</a>
          </li>
        
          <li>
            <a href="/notes-on-computer-expertise/2022/05/26/%E6%95%B0%E6%8D%AE%E5%BA%93/navicat%E5%AE%89%E8%A3%85/">(no title)</a>
          </li>
        
          <li>
            <a href="/notes-on-computer-expertise/2022/05/25/%E8%99%9A%E5%B9%BB4%E5%BC%95%E6%93%8E%E5%BC%80%E5%8F%91/%E8%99%9A%E5%B9%BB%E5%9B%9B%20mod%E5%88%B6%E4%BD%9C/">(no title)</a>
          </li>
        
          <li>
            <a href="/notes-on-computer-expertise/2022/05/23/python/python%E6%89%B9%E9%87%8F%E7%94%9F%E6%88%90%E6%95%B0%E6%8D%AE/">(no title)</a>
          </li>
        
          <li>
            <a href="/notes-on-computer-expertise/2022/05/23/vba%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C%E7%AC%94%E8%AE%B0/EXCEL%E5%9F%BA%E7%A1%80%E6%95%99%E7%A8%8B/">(no title)</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      
      &copy; 2022 John Doe<br>
      Powered by <a href="https://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>

    </div>
    <nav id="mobile-nav">
  
    <a href="/notes-on-computer-expertise/" class="mobile-nav-link">Home</a>
  
    <a href="/notes-on-computer-expertise/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    


<script src="/notes-on-computer-expertise/js/jquery-3.4.1.min.js"></script>



  
<script src="/notes-on-computer-expertise/fancybox/jquery.fancybox.min.js"></script>




<script src="/notes-on-computer-expertise/js/script.js"></script>





  </div>
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
        tex2jax: {
            inlineMath: [ ["$","$"], ["\\(","\\)"] ],
            skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
            processEscapes: true
        }
    });
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax();
        for (var i = 0; i < all.length; ++i)
            all[i].SourceElement().parentNode.className += ' has-jax';
    });
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML"></script>
</body>
</html>